import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: XMQ
 * Date: 2022-05-21
 * Time: 10:16
 */
//几道leetcode调试+看了一下动态绑定的反编译
class Animal{
    public String name;

    public void eat(){
        System.out.println("Aniaml");
    }
}
class Cat extends Animal{
    @Override
    public void eat() {
        System.out.println("Cat");
    }
}
public class Test {

    public static void main4(String[] args) {
        Animal animal = new Cat();
        animal.eat();
    }

    //nums.length == 2 * n.
    //nums 包含 n + 1 个 不同的 元素
    //nums 中恰有一个元素重复 n 次
    public static int repeatedNTimes1(int[] nums) {
        //暴力计数
        int mid = nums.length/2;
        int[] arr = new int[10005];
        for(int i = 0; i < nums.length; i++){
            arr[nums[i]]++;
            if(arr[nums[i]] == mid) return nums[i];
        }
        return -1;
    }
    public static int repeatedNTimes(int[] nums){
        Arrays.sort(nums);
        int mid = nums.length/2;
        return nums[mid] == nums[mid+1] ? nums[mid]:nums[mid-1];
    }
    public static void main(String[] args) {
        int[] nums = {5,1,5,2,5,3,5,4};
        System.out.println(repeatedNTimes1(nums));
        System.out.println(repeatedNTimes(nums));
    }



    //求数组中有一个数只出现一次，其余数都出现两次
    //& | ^
    public static int singleNonDuplicate(int[] nums) {
        int i = 0;
        int ret = 0;
        for(;i < nums.length;i++){
            ret ^= nums[i];
        }
        return ret;
    }

    //有两个数只出现一次时 -> 不会
    public static void main2(String[] args) {
        int ret = 0;
        int count = 0;
        int[] nums = {1,2,3,4,5,3,2,1};
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }

        int[] array1 = new int[nums.length];
        int[] array2 = new int[nums.length];

        for (int i = 0; i < 32; i++) {
            //求第一个1的位置
            ret ^= 1;
            count++;
            if(ret == 0){
                break;
            }
            ret = ret >>> 1;
        }
        int a1 = 0;
        int a2 = 0;
        for (int i = 0; i < nums.length; i++) {
            //分组
            //怎么确定一个数的二进制的第一位和某个数是否相同
            //也就是怎么取出一个数二进制下的某个bit位
            if(nums[i] >= Math.pow(2,(count-1))){
                array1[a1] = nums[i];
                a1++;
            }else{
                array2[a2] = nums[i];
                a2++;
            }
        }
        //求得两数
        int num1 = 0;
        int num2 = 0;
        for (int i = 0; i < array1.length; i++) {
            num1 ^= array1[i];
        }
        for (int i = 0; i < array2.length; i++) {
            num2 ^= array2[i];
        }
        System.out.println(num1);
        System.out.println(num2);
    }
    public static void main1(String[] args) {
        int[] nums = {1,2,3,4,3,2,1};
        System.out.println(singleNonDuplicate(nums));
    }
}
